package org.example.myleet.p1370;

public class Solution {
    public String sortString(String s) {
        int[] frequency = new int[26];
        for (int i=0; i<s.length(); i++) {
            ++frequency[s.charAt(i) - 'a'];
        }
        char[] result = new char[s.length()];
        int ri = 0;
        while (!finish(frequency)) {
            //来一遍由小到大
            for (int i=0; i<frequency.length; i++) {
                if (frequency[i] > 0) {
                    result[ri] = (char) ('a' + i);
                    ++ri;
                    --frequency[i];
                }
            }
            //再来一遍由大到小
            for (int i=frequency.length - 1; i>=0; i--) {
                if (frequency[i] > 0) {
                    result[ri] = (char) ('a' + i);
                    ++ri;
                    --frequency[i];
                }
            }
        }
        return new String(result);
    }

    private boolean finish(int[] frequency) {
        for (int f : frequency) {
            if (f > 0) {
                return false;
            }
        }
        return true;
    }
}
